#include <iostream>
#include <memory>
using namespace  std;
template<class K, class V>
struct BSTreeNode
{
    K _key;              // 节点的键
    V _value;            // 节点的值
    BSTreeNode* left;   // 左子节点
    BSTreeNode* right;  // 右子节点
    BSTreeNode(const K& k, const V& v)
        : _key(k), _value(v), left(nullptr), right(nullptr) {}
};
template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value) {
        if(!_root) {
            _root = new Node(key, value);
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur) {
            parent = cur;
            if(cur->_key < key) {
                cur = cur->right;
            }else if(cur->_key > key) {
                cur = cur->left;
            }else {
                return false;
            }
        }
        if(key < parent->_key) {
            parent->left = new Node(key, value);
        }else {
            parent->right = new Node(key, value);
        }
        return true;
    }
	Node* Find(const K& key) {
        Node* cur = _root;
        while(cur) {
            if(cur->_key < key) {
                cur = cur->right;
            }else if(cur->_key > key) {
                cur = cur->left;
            }else {
                return cur;
            }
        }
        return nullptr; // 没找到符合的值
    }
	bool Erase(const K& key) {
        // 分类讨论，第一种：头节点就是；第二种：删除的是叶子节点；第三种：删除的是有一个节点的；第四种（相对复杂）：删除的节点有两个子节点（可能是子树）
        // 首先就是看有没有这个节点了，这里貌似还不能复用上面的查找，因为我们还要有相对应的父节点，所以这里的结构如果是用的三叉结构就可以复用了
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur && cur->_key != key) {
            parent = cur;
            if(cur->_key < key) {
                cur = cur->right;
            }else {
                cur = cur->left;
            }
        }
        if(!cur) {
            return false;
        }
        if(!cur->left && !cur->right) { // 删除的节点没有子节点
            if(!parent) _root = nullptr; // 删除的是头节点了
            else if(parent->left == cur) parent->left = nullptr;
            else parent->right = nullptr;
            delete cur;
        }else if(!cur->left || !cur->right) { // 删除的节点有一个子节点
            Node* child = cur->lefe ? cur->left : cur->right;
            if(!parent) _root = child;
            else if(parent->left == cur) parent->left = child;
            else parent->right = child;
            delete cur; 
        }else {
            Node* par = cur;
            Node* c = cur->right;
            while(c->left) {
                par = c;
                c = c->left;
            }
            cur->_key = c->_key;
            cur->_value = c->_value;
            if(par->left == c) par->left = c->right;
            else par->right = c->right;
            delete c;
        }
        return true;
    }
	void _InOrder(Node* root) {
        if(!root) {
            return;
        }
        _InOrder(root->left);
        cout << "key: " << root->_key << ", " << "value: " << root->_value << endl;
        _InOrder(root->right);
    }
	void InOrder() {
        _InOrder(_root);
    }
private:
	Node* _root = nullptr;
};

void TestBSTree()
{
	BSTree<string, string> dict;
	dict.Insert("insert", "插入");
	dict.Insert("erase", "删除");
	dict.Insert("left", "左边");
	dict.Insert("string", "字符串");

	string str;
	while (cin>>str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << str << ":" << ret->_value << endl;
		}
		else
		{
			cout << "单词拼写错误" << endl;
		}
	}

	// string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
	// 统计水果出现的次
	// BSTree<string, int> countTree;
	// for (auto str : strs)
	// {
	// 	auto ret = countTree.Find(str);
	// 	if (ret == NULL)
	// 	{
	// 		countTree.Insert(str, 1);
	// 	}
	// 	else
	// 	{
	// 		ret->_value++;
	// 	}
	// }
	// countTree.InOrder();
}
int main() {
    TestBSTree();
    return 0;
}